#include <iostream>

using namespace std;
// 86. 分隔链表
// 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
// 输入：head = [1,4,3,2,5,2], x = 3
// 输出：[1,2,2,4,3,5]

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            if(head == NULL || head->next == NULL) return head;
            ListNode *h1 = new ListNode(-1), *r1 = h1;  // h1是保存小于x结点的链表
            ListNode *h2 = new ListNode(-2), *r2 = h2;  // h2是保存大于等于x结点的链表
            ListNode* p = head; // p用来遍历原单链表

            while(p != NULL) {
                if(p->val < x) {
                    r1->next = p; r1 = p;   // 尾插法插入p
                    p = p->next;
                } else {
                    r2->next = p; r2 = p;
                    p = p->next;
                }
            }
            r1->next = NULL;
            r2->next = NULL;

            if(h1->next != NULL) {
                head = h1->next;
                r1->next = h2->next;
            }else { // 不存在小于x的结点
                head = h2->next;
            }

            delete h1; delete h2;
            return head;
        }
    };

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
